package wheel.arithmetic;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;
import wheel.dataStruct.impl.BinaryHeap;

/**
 * 选择排序-堆排序
 *
 * 就是使用二叉堆的根节点是最大或最小的特性，一直poll出最大或最小的值，
 */
public class HeapSort {
    public static void main(String[] args) {

        Integer[] arr = new Integer[10000000];
        for(int i=0; i<arr.length; i++){
            arr[i] = RandomUtil.randomInt(0, arr.length);
        }

//        arr = new Integer[]{10, 9, 8, 7, 6, 5, 4, 3};


//        System.out.println("输入: "+ ArrayUtil.toString(arr));


        long startTime = System.currentTimeMillis();
        arr = execute(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时: "+(endTime-startTime)+"ms");

//        System.out.println("输出: "+ArrayUtil.toString(arr));

    }

    public static Integer[] execute(Integer[] arr){

        BinaryHeap<Integer> binaryHeap = new BinaryHeap<>(arr.length);

        for(Integer e : arr)
            binaryHeap.insert(e);

        int i = 0;
        while(!binaryHeap.isEmpty()){
            arr[i] = binaryHeap.poll();
            i++;
        }


        return arr;
    }

    //耗时: 13ms 9ms 8ms 一万个
    //耗时: 44ms 49ms 40ms 十万个
    //耗时: 106ms 94ms 90ms 二十万个
    //耗时: 916ms 665ms 814ms 一百万个
    //耗时: 10064ms 10090ms 10655ms 一千万个
}
